home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 1.iso / toolbox / src / exampleCode / opengl / toogl / search.c++ < prev    next >
C/C++ Source or Header  |  1996-11-11  |  3KB  |  92 lines
  1. /*
  2.  * Copyright (c) 1992, 1993 Silicon Graphics, Inc.
  3.  *
  4.  * Permission to use, copy, modify, distribute, and sell this software and
  5.  * its documentation for any purpose is hereby granted without fee, provided
  6.  * that (i) the above copyright notices and this permission notice appear in
  7.  * all copies of the software and related documentation, and (ii) the name of
  8.  * Silicon Graphics may not be used in any advertising or publicity relating 
  9.  * to the software without the specific, prior written permission of 
  10.  * Silicon Graphics.
  11.  *
  12.  * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF
  13.  * ANY KIND, EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, 
  14.  * ANY WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
  15.  *
  16.  * IN NO EVENT SHALL SILICON GRAPHICS BE LIABLE FOR ANY SPECIAL, INCIDENTAL, 
  17.  * INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND, OR ANY DAMAGES WHATSOEVER 
  18.  * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER OR NOT ADVISED OF 
  19.  * THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF LIABILITY, ARISING OUT 
  20.  * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  21.  */
  22.  
  23. /*
  24.  * Algorithm from "A New Approach to Text Searching"
  25.  * Communications of the ACM
  26.  * October 1992 Volume 35,  Number 10
  27.  * pp 74-82
  28.  * 
  29.  * Fast text matching for patterns with classes like:
  30.  * [nvtc].[234].[difs].
  31.  * would match n3f, v3s, t4d ...
  32.  * 
  33.  * Gives lots of false hits in the toogl application due to large number
  34.  * of characters in classes:
  35.  * "tory" matches a pattern from "poly", "circ", "tpon":
  36.  * [tpc].[oip].[lro].[ycn].
  37.  * but still gives a factor of 10 improvement over not doing this.
  38.  * 
  39.  */
  40. #include <stdlib.h>
  41. #include <iostream.h>
  42.  
  43. #include "search.h"
  44.  
  45. Search::Search() 
  46. {
  47.     int i;
  48.     for( i = 0; i < sizeof(table)/sizeof(table[0]); table[i++] = ~0);
  49.     cstate = 0;
  50.     lim = 0;
  51. }
  52.  
  53. void Search::add(const char *s) 
  54. {
  55.     int i;
  56.     for( i = 0; i < MAXPATTERN && s[i]; i++) {
  57.     int c = (s[i])&(NALPH-1);
  58.     table[c] &= ~(1 << i);
  59.     lim |= (1 << i);
  60.     }
  61. }
  62.  
  63. void Search::print_table()
  64. {
  65.     int i, j;
  66.     for(i =' '; i < NALPH; i++) {
  67.     cerr << (char)i << " ";
  68.     for(j = 0; j < MAXPATTERN; j++) {
  69.         cerr << (char)((table[i] & (1 << j)) ? '1' : '0');
  70.     }
  71.     cerr << "\n";
  72.     }
  73.         
  74. }
  75.  
  76. int Search::check(const char *s) 
  77. {
  78.     int i, c;
  79.     unsigned int initial = ~0,  state;
  80.     unsigned llim = ~(lim >> 1);
  81.     
  82.     state = initial;
  83.     for( i = 0; s[i]; i++) {
  84.     c = s[i] & (NALPH-1);
  85.     state = (state << 1) | table[c];
  86.     if (state < llim) {
  87.         return 1;
  88.     }
  89.     }
  90.     return 0;    
  91. }
  92.